package com.javabasic.algorithm.leetcode;

import java.util.Set;
import java.util.TreeMap;
import java.util.TreeSet;

/**
 * @Author xiongmin
 * @Description
 * @Date 2021-04-05 0:03
 * @Version 1.0
 **/
public class RabbitsInForest {

    public static void main(String[] args) {

    }

    public int numRabbits(int[] answers) {
        // 标记说相同颜色个数的兔子
        TreeMap<Integer, Integer> valueToNums = new TreeMap<>();
        int result = 0;
        Integer orDefault;
        for (int answer : answers) {
            if (answer == 0) {
                result += 1;
            } else  {
                int key = answer + 1;
                orDefault = valueToNums.getOrDefault(key, 0);
                valueToNums.put(key,orDefault+1);
            }
        }

        Set<Integer> keys = valueToNums.keySet();
        Integer size;
        for (Integer key : keys) {
            size = valueToNums.get(key);
            // 说相同颜色个数的兔子，可以放到一起，让是如果个数大于兔子说的就要分到定外一类
            if (size > key) {
                // 如果总数刚好够分好几类，就正好，如果过不够就多加一类
                if (size%key == 0) {
                    result += size;
                } else {
                    result += ((size/key)+1)*key;
                }
            } else {
                result += key;
            }
        }
        return result;
    }
}
